Exercise 6 (Homework 6).
(R (decidable/recursive languages),
RE (semi-decidable/ recursively enumerable languages))
Classification VI: variations on K
For each of the following languages L, decide whether L\in \mathbf{R}, L\in \mathbf{RE}\setminus \mathbf{R}, L\in \mathbf{coRE}\setminus \mathbf{R}, or L\notin \mathbf{RE}\cup \mathbf{coRE}.
- L=K\times K
- L=\overline K\times K
- L=\overline K \times \overline K
- L=\overline{\overline K \times K}
Note
Recall that K=\{n\mid M_n(n)\!\downarrow\}\ , where M_n is the Turing machine with Gödel number n and the \downarrow means that the machine terminates.